package niuke.week02;

/**
 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 */
public class PathOfMatrix {

    public static void main(String[] args) {
        String str1 = "ABCESFCSADEE";
        char[] matrix = str1.toCharArray();

        String str2 = "ABCCED";
        char[] str = str2.toCharArray();

        System.out.println(hasPath(matrix,3,4,str));
    }

    public static  boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        boolean [][]visit = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(hasPath(matrix,rows,cols,i,j,0,str,visit))
                    return true;
            }
        }
        return false;
    }

    public static boolean hasPath(char[] matrix, int rows, int cols,
                                          int i,int j ,int pathLength,
                            char[] str,   boolean[][] visited){
        if(pathLength==str.length)
            return true;

        boolean hasPath = false;

        if(i<rows && j<cols && i>=0 && j>=0 && !visited[i][j] &&
           str[pathLength]==matrix[i*cols+j] ){

            visited[i][j] = true;//i,j访问过了
            ++pathLength;//继续向后匹配

            hasPath = hasPath(matrix,rows,cols,i,j+1,pathLength,str,visited) ||//右
                      hasPath(matrix,rows,cols,i+1,j,pathLength,str,visited) ||//下
                      hasPath(matrix,rows,cols,i-1,j,pathLength,str,visited) ||//上
                      hasPath(matrix,rows,cols,i,j-1,pathLength,str,visited) ;//左

            if(!hasPath){
                visited[i][j] = false;
                --pathLength;
            }
        }
        return hasPath;

    }
}